Circular mixed hypergraphs II:The upper chromatic number

A mixed hypergraph is a triple H=(X,C,D), where X is the vertex set and each of C, D is a family of subsets of X, the C-edges and D-edges, respectively. A proper k-coloring of H is a mapping c:X→[k] such that each C-edge has two vertices with a common color and each D-edge has two vertices with distinct colors. A mixed hypergraph H is called circular if there exists a host cycle on the vertex set X such that every edge (C- or D-) induces a connected subgraph of this cycle.We suggest a general procedure for coloring circular mixed hypergraphs and prove that if H is a reduced colorable circular mixed hypergraph with n vertices, upper chromatic number and sieve number s, then

     

Parallel and fast sequential algorithms for undirected edge connectivity augmentation

1 ,E₂,..., such that ⋃_i≤τE_i optmially increases the connectivity by τ, for any integer τ. The main result of the paper is that this sequence of edge sets can be divided into O(n) groups such that within one group, all E_i are basically the same. Using this result, we improve on the running time of edge connectivity augmentation, as well as we give the first parallel (RNC) augmentation algorithm. We also present new efficient subroutines for finding the so-called extreme sets and the cactus representation of min-cuts required in our algorithms. Augmenting the connectivity of hypergraphs with ordinary edges is known to be structurally harder than that of ordinary graphs. In a weaker version when one exceptional hyperedge is allowed in the augmenting edge set, we derive similar results as for ordinary graphs. Received November 1995 / Revised version received July 1998 Published online March 16, 1999     

Counting acyclic hypergraphs

Acyclic hypergraphs are analogues of forests in graphs. They are very useful in the design of databases. The number of distinct acyclic uniform hypergraphs withn labeled vertices is studied. With the aid of the principle of inclusion-exclusion, two formulas are presented. One is the explicitformula for strict (d)-connected acyclic hypergraphs, the other is the recurrence formula for linear acyclic hypergraphs.     

Partitions of hypergraphs under variable degeneracy constraints

The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph $H$ and a sequence $f=\left(f_1,f_2,\text{…},f_p\right)$ of $p\ge 1$ vertex functions $f_i:V\left(H\right)\to {\mathbb{N}}_0$ such that $f_1\left(v\right)+f_2\left(v\right)+\mathrm{?}+f_p\left(v\right)\ge d_H\left(v\right)$ for all $v\in V\left(H\right)$, we want to find a sequence $\left(H_1,H_2,\text{…},H_p\right)$ of vertex disjoint induced subhypergraphs containing all vertices of $H$ such that each hypergraph $H_i$ is strictly $f_i$‐degenerate, that is, for every nonempty subhypergraph $H\prime ?H_i$ there is a vertex $v\in V\left(H\prime \right)$ such that $d_{H\prime }\left(v\right)<f_i\left(v\right)$. Our main result in this paper says that such a sequence of hypergraphs exists if and only if $\left(H,f\right)$ is not a so‐called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems.     

Vanishing of cohomology groups of random simplicial complexes

We consider k‐dimensional random simplicial complexes generated from the binomial random (k + 1)‐uniform hypergraph by taking the downward‐closure. For 1 ≤ j ≤ k ? 1, we determine when all cohomology groups with coefficients in from dimension one up to j vanish and the zero‐th cohomology group is isomorphic to . This property is not deterministically monotone for this model, but nevertheless we show that it has a single sharp threshold. Moreover we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. We also study the asymptotic distribution of the dimension of the j‐th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced by Linial and Meshulam, previously only known for dimension two.     

Squares of Hamiltonian cycles in 3‐uniform hypergraphs

We show that every 3‐uniform hypergraph H = (V,E) with |V(H)| = n and minimum pair degree at least (4/5 + o(1))n contains a squared Hamiltonian cycle. This may be regarded as a first step towards a hypergraph version of the Pósa‐Seymour conjecture.     

Characterizing and decomposing classes of threshold,split, and bipartite graphs via 1-Sperner hypergraphs

A hypergraph is said to be 1-Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of $1$-Sperner hypergraphs to graphs. First, we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding $1$-Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of $1$-Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique-width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.     

Maximal τ-Critical Linear Hypergraphs

 A construction using finite affine geometries is given to show that the maximum number of edges in a τ-critical linear hypergraph is (1−o(1))τ². This asymptotically answers a question of Roudneff [14], Aharoni and Ziv [1]. Received: June 28, 1999 Final version received: October 22, 1999